#-*- coding: utf-8 -*-
#!/usr/bin/env python

'''
author: Bruno Alves, n.º 6152
'''

from Node import *
from LinkedLists import *
from Stack import *
import math
import sys
import time
import random

'''
Class KDTree - To create a k dimension tree
'''    
class KDTree:
    '''
    KDTree Constructor
    '''
    def __init__(self):
        self.root = Node(None, None)

    '''
    Method to insert nodes on the tree
    '''
    def insertion(self, node, depth = 0):        
        if not node:
            return None  

        i = linkedList.malloc(node)
        linkedList.insert(i)
            
        x = len(node[0].key)
        axis = depth % x
        
        s =  len(node) -  1
        self.quick_sort(node, axis, s)
       
        k = len(node) // 2       
       
        y = node[k] 
           
        y.left = self.insertion(node[:k], depth + 1) 
        y.right = self.insertion(node[k +1:], depth + 1) 
        
        if y.left != None:
            node[k].left.parent = y
        if y.right != None:
            node[k].right.parent = y
        else:
            y.parent = self.root 

        self.checkBalance()
        return y
            
    '''
    Method to remove a node from the tree
    '''        
    def removal(self, z): 
        i = linkedList.malloc(z)
        
        linkedList.remove(i)
        linkedList.free(i)
        
        if z.left == None:
            self.rebuild(z, z.right)
        elif z.right == None:
            self.rebuild(z, z.left)
        else:
            y = self.minimum(z.right)
            if y.parent != z:
                self.rebuild(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.rebuild(z, y)
            y.left = z.left
            y.left.parent = y
         
    '''
    QuickSort function
    ''' 
    def quick_sort(self, A, p, r):
        if (p < r):
            q = self.quick_sort_partition(A, p,r)
            self.quick_sort(A, p, q - 1)
            self.quick_sort(A, q + 1, r)

    
    '''
    QuickSort Partition
    '''
    def quick_sort_partition(self,A, p, r):
        x = A[r]
        i = p - 1
        for j in range(p, r):
            if(A[j] <= x):
                i = i + 1
                A[i], A[j] = A[j], A[i]
                pass
            pass
        A[i + 1], A[r] = A[r], A[i + 1]
    
        return i + 1           

    
    '''
    Puts tree values on a list
    '''
    def inorder_walk(self, x, lista):
        if x != None:
            self.inorder_walk(x.left, lista)
            lista.append( x )
            self.inorder_walk(x.right, lista)
            
    pass

    '''
    Method to rebuild a tree.
    '''     
    def rebuild(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v != None:
            v.parent = u.parent   

    '''
    Method to reinsert values on a tree
    '''
    def reInsert(self):
        stack = []
        if len(stack) > 0:
          a = self.stack.pop(0)
          if len(a) == 1:
            self.insert(self.root, a.pop(0), False)
          elif len(a) == 0:
            pass
          else:
            k = int(math.floor(len(a)/2))
            x = a.pop(k)
            x.parent = x.left = x.right = None
            self.insert(self.root, x, False)
            b = a[:k]
            if len(b) > 0: 
              self.stack.append(b)
            b = a[k:]
            if len(b) > 0: 
              self.stack.append(b)
          if len(self.stack) > 0:
            self.__reInsert()
        else:
          self.checkBalance()
          pass


    '''
    Method to see if tree is balanced
    '''
    def isBalanced(self, x):
        a = x.LC
        b = x.RC
        if(a + b) < 2:
            return True

        if(a + b) <= 4 and min(a,b) == 1:
            return True

        return min(a, b) > 2**(int(math.floor(math.log(max(a,b),2)))) - 1

    
    '''
    Method to balance tree
    '''
    def checkBalance(self):
        if self.root == None:
            return
        
        stack = []
        stack.append(self.root)
        while len(stack) > 0:
            x = stack.pop(0)
            if x.left != None:
                stack.append(x.left)

            if x.right != None:
                stack.append(x.right)

            if self.isBalanced(x):
                continue
            parent = x.parent
            dim = x.dim
            self.__clear(x)
            lista = []

            self.inorderWalk(x, lista)
            self.quick_sort(lista, (dim + 1) % self.dimention)
            self.stack.append(lista)
            self.__reInsert()

    '''
    Method to search the nearest neighbour
    '''
    def nearestNeighbour(self, node, lista, dimensions):
        self.inorder_walk(self.root, lista)
        distance = sys.maxint
        x = self.root
        for i in lista:
            if node != i:
                temp = 0
                for k in range(dimensions):
                    temp += (i.key[k] - node.key[k])**2
                temp = math.sqrt(temp)
                if distance > temp:
                    distance = temp
                    x = i
        return x


'''
Tests
'''
maxNodes = 10
maxValue = 1000

kdList = [None for k in range(maxNodes)]
nodes = [None for k in range(maxNodes)]

for k in range (len(kdList)):
    kdList[k] = [random.randint(0, maxValue), random.randint(0, maxValue)]

for x in range (len (kdList)):
    nodes[x] = Node(kdList[x], "valor")
    pass

tree = KDTree()

N=len(kdList)+7
linkedList = LinkedList(N)

t1 = time.clock()
newTree = tree.insertion(nodes)
t2 = time.clock()

print "#################### INSERIR 1 ####################"
for x in range (len(nodes)):
    print nodes[x]

print "Time Insert:"
print (t2-t1)

remove = []

t1 = time.clock()
tree.removal(nodes[4])
tree.inorder_walk(newTree, remove)
t2 = time.clock()
print "#################### APAGAR 1 ####################"
for x in remove:
    print x

print "Time Delete:"
print (t2-t1)

print "#################### VIZINHO 1 ####################"
t1 = time.clock()
print tree.nearestNeighbour(nodes[random.randint(0, maxNodes - 1)], nodes, 0)
t2 = time.clock()
print "Time Search:"
print (t2-t1)

print "###################################################"

maxNodes = 900
maxValue = 1000

kdList = [None for k in range(maxNodes)]
nodes = [None for k in range(maxNodes)]

for k in range (len(kdList)):
    kdList[k] = [random.randint(0, maxValue), random.randint(0, maxValue)]

for x in range (len (kdList)):
    nodes[x] = Node(kdList[x], "valor")
    pass

tree = KDTree()

N=len(kdList)+7
linkedList = LinkedList(N)

t1 = time.clock()
newTree = tree.insertion(nodes)
t2 = time.clock()

print "#################### INSERIR 2 ####################"

print "Time Insert:"
print (t2-t1)

remove = []

t1 = time.clock()
tree.removal(nodes[6])
t2 = time.clock()
print "#################### APAGAR 2 ####################"

print "Time Delete:"
print (t2-t1)

print "#################### VIZINHO 2 ####################"
t1 = time.clock()
print tree.nearestNeighbour([random.randint(0, maxNodes)], nodes, 0)
t2 = time.clock()
print "Time Search:"
print (t2-t1)

print "###################################################"







